# 填充每个节点的下一个右侧节点指针 II

class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return
        layer = [root]
        while layer:
            length = len(layer)
            for i in range(length):
                if i == length - 1:
                    layer[i].next = None
                else:
                    layer[i].next = layer[i+1]
            for _ in range(length):
                node = layer.pop(0)
                if node.left:
                    layer.append(node.left)
                if node.right:
                    layer.append(node.right)
        return root
